Cache memories (high speed, low capacity memories) are incorporated in data processing systems to reduce data transfer times. Typically, multiprocessor data processing systems comprise a single cache memory per principal memory unit. A problem arises when multiple access from plural processors to the same cache memory is desired.
This problem is commonly resolved by means of hold-over lines or queues governed frequently by priority circuits. In all cases, hold-over or waiting periods associated with the lines or queues have an effect on the processing periods because there is no way of which I am aware of authorizing multiple access operations to a single cache memory.
In accordance with another prior art concept, use of cache memories is decentralized beyond the principal memory units, a result achieved by associating a cache memory with each processor of the system. This system is disclosed in an article having the title "Performance Results for an M.I.M.D. Computer Organization Using Pipeline Binary Switches and Cache Memories", published in the British Journal "PROC. IEE", Volume 125, Number 11, November 1978. In this article there is no statement posing or resolving the problem of data coherence stored in the different cache memories and in the principal memory unit or units of the system. This problem has been posed and resolved in the commonly owned French Patent Application No. 78 20206, filed July 6, 1978. The solution of the data coherence problem set forth in the French Application does not resolve a problem posed in multiple access to a cache memory of a single processor.
It is an object of the invention to govern multiple access actions to a memory unit of a single cache memory to prevent conflicts while promoting the multiple access actions to increase the speed of simultaneous handling of several tasks respectivvely performed by several processors.
When a processor of a digital data processing system processes a task, it enters into dialogue with a memory array of the system. The memory array includes at least one principal memory unit and intrinsic resources of the processor, such as a cache memory. This dialogue results in the processor deriving requests for access to data contained in the memory array. The processing of these requests has recourse under priority to the intrinsic resources of the processor, and, if subsequently applicable, to the remainder of the system via a principal multiple lead or bit bus interconnecting the different units of the system.
If the system comprises at least one additional processor, the latter is equally likely to derive requests for access to data while processing a task. As long as the two processors of the system have recourse to their own resources, there is no conflict between the task processing operations performed by the two processors.
However, while a request is being processed, a first processor deriving this request may attempt to access a data item not contained in its own cache memory. In such case, the request deriving processor calls on the remainder of item contained, e.g., either (1) in the principal memory unit, or (2) in the cache memory of a second processor of the system, or (3) more commonly, in another cache memory of a processor of the system. The calls to the remainder of the system occur if the data item sought has been modified in the cache memory of the first processor without an image of the data item in the principal memory having been modified in accordance with the procedure specified in the aforesaid patent application. It is possible that the another cache memory is processing an internal request derived by the processor associated with the another cache memory when the another cache memory receives a request from the first processor for access to the stored data in the another cache memory. The another cache memory considers the request for access from the first processor as a so-called external request because this request is not derived by its associaterd processor.
In these circumstances, a conflict may arise at the level of the another cache memory of the system. The conflict is between the processing of an internal request derived by the associated processor and the processing of an external request derived from the first processor of the system.
An object of the invention is to govern this kind of conflict while promoting simultaneous implementation of internal and external requests to a single cache memory of the system that receives the conflicting requests.
To this end, the invention proposes a process for managing the conflicts raised by multiple access to a single cache memory of a digital data processing system including at least: one main memory unit, two processors, an input-output unit and a main connector bus connecting these different elements of the system. Each processor includes resources such as a cache memory having a memory section and an index section for identification of the data contained in the memory section. The processing of a task by a first processor involves deriving at least one request for gaining access to at least one data item present either in the cache memory of the first processor or of another processor, or in the memory unit of the system. This request is enabled by the cache memory of the first processor which considers the request as internal. This internal request is executed by the cache memory of the first processor. The cache memory of the first processor is able to receive an external request derived by another processor of the system that is processing another task. The another cache memory requests access to at least one data item in the cache memory of the first processor by means of the connector bus.
To avoid a conflict between the processing operations of internal and external requests on the another cache memory while promoting simultaneous processing of these requests, the process involves enabling an external request derived by the first processor and addressed in particular to the second cache memory. All of the other cache memories of the system take this external request from the first processor into account once the request has been enabled. This external request is analyzed by the other cache memories. The external request is processed by the cache memory affected by the external request, i.e., the second cache memory. Simultaneous processing by the second cache memory of internal and external requests is authorized if these requests are addressed to different resources of the processor such as a memory section and an index section of the second cache memory. An internal request currently being processed by the second cache memory is interrupted or enabling is prevented if the current processing of an external request requires all of the resources of the processor in question. Alternatively, an external request currently being processed by the second cache memory is interrupted or enabling of an external request is delayed if the current processing of an internal request requires all of the resources of the processor in question.
According to another feature of the invention, execution of an internal request or of an external request by a cache memory of the system involves processing a series of read and write operations during a series of cycles defined by the cache memory. The first of these processing cycles is initiated in response to an enabled internal request or of an enabled external request. Either an internal request or an external request is enabled during a first processing cycle. Priority is awarded to enabling of an external request over an internal request if these requests must be taken into account at the same time by a single cache memory. Simultaneous processing of these requests is authorized during the following cycles if the requests have recourse to different resources of the cache memory of the processor.
According to another feature of the invention, at the beginning of each processing cycle a determination is made, as a function of the state of the system, as to whether the next operation to be performed involves processing an internal request or enabling another internal request, or if the next operation involves processing an external request or enabling another external request. The process involves establishing at least one enabling condition as a function of the nature of the operation required by the processing of an external request then being executed. This condition is established for either the next processing operation of an internal request or for the next operation involving enabling another internal request. There is also established at least one enabling condition as a function of the nature of the operation required by the processing of an internal request then being executed. This condition is established for either the next processing operation of an external request or for the next operation enabling another external request.
According to another feature of the invention, the process involves delaying, at the beginning of a processing cycle, the next processing operation of an internal request and thus interrupting this internal request. In particular, the delay is provided for access demand to the connector bus if the bus is already occupied or if the external request then being executed has reserved the resources of the cache memory; resources of the cache memory thay may have been reserved are the memory and index sections. This action prevents a conflict of simultaneous access to the recourses.
According to another feature of the invention, the process involves delaying, at the start of a processing cycle, enabling of an internal request relating to a read operation for a data item of the cache memory of the processor deriving the internal request. This delay occurs if an enabling external request operates on the index section or memory section of the cache memory of the processor.
According to another feature of the invention, the process involves delaying, at the start of a processing cycle, enabling of an internal request relating to a write operation for a data item contained in the cache memory of the processor. This delay occurs if an enabled external request is already operating on the memory section or the index section of the cache memory of the processor, or will be operating on the memory section or the index section of the cache memory in the following processing cycle of the system.
According to another feature of the invention, the process involves delaying enabling of another external request if the operation called for by the processing of an internal request is a data transfer operation on the connector bus connected between the cache memory of the processor and the main memory unit of the system deriving the internal request.
According to another feature of the invention, the process involves interrupting, at the start of the processing cycle, the next processing operation of an external request. This interrupt occurs if the processing operation affects the memory section of the cache memory while an internal request already operates on the memory section of the cache memory of the processor.
The invention also envisages a device for application of the process in a system comprising at least: one main memory unit and two processors, each of which has intrinsic resources such as a cache memory. The cache memory includes a memory section and an index section for identifying the data contained in the memory section. Each cache memory of the system comprises first means for assuring synchronization between the different operations performed by the cache memory to assure processing of an internal request derived by a processor co-ordinated with this cache memory. The cache memory also includes second means for assuring synchronization between the different operations performed by the cache memory to assure processing of an external request transmitted by another processor of the system. A third means assures a dialogue from the second means to the first means by deriving signals for interrupting the operation of the first means. A fourth means assures a dialogue from the first means to the second means by deriving signals for interrupting the operation of the second means.
According to another feature of the device, the first means of the cache memory comprises series connected flip-flops in combination with a timer or clock that derives periodic timing pulses supplied to the flip-flops to establish a succession of cycles. A gate circuit associated with each flip-flop enables orders for switching the associated flip-flop. Internal control circuits have output terminals connected to each of the gate circuits to determine the switching conditions of each flip-flop as a function of the operation to be processed by the cache memory.
According to a further feature of the device, the second means of the cache memory includes a number of series connected flip-flops responsive to the timing pulses. A gate circuit associated with each flip-flop enables the switching order for the associated flip-flop. External control circuits supply signals to each of the gate circuits to determine the switching conditions of each flip-flop as a function of the operation to be processed by the cache memory.
According to another feature of the device, the third means comprises a first circuit for requesting interruption of the operation of the first synchronizing means provided for processing an internal request. At least one output signal of the first interruption request circuit is coupled to each circuit for enabling the first means.
According to another feature of the device, the fourth means comprises a second circuit for requesting interruption of the operation of the second synchronizing means provided for processing an external request. At least one output signal of the second interruption request circuit is coupled to an input terminal of each enabling circuit of the second means.
A substantial advantage of the invention involves authorizing maximum overlap between the processing by a single cache memory of an internal request, as well as of an external request. This makes it possible to increase the speed of processing of the tasks performed by a processor and allows optimum utilization of the connector bus, thereby improving the performance factors of the system.
The above and still further objects, features and advantages of the present invention will become apparent upon consideration of one specific embodiment thereof, especially when taken in conjunction with the accompanying drawings.